本文|都会_论文精读Scalingdistributedmachinelearningwiththeparameterserver

篇首语：本文由编程笔记#小编为大家整理，主要介绍了论文精读Scaling distributed machine learning with the parameter server相关的知识，希望对你有一定的参考价值。

Scaling distributed machine learning with the parameter server

• 前言
• Abstract
• 1. Introduction
• • 1.1 Contributions
  • 1.2 Engineering Challenges
  • 1.3 Related Work
  
  
• 2. Machine Learning
• • 2.1 Goals
  • 2.2 Risk Minimization
  • 2.3 Generative Models
  
  
• 3. Architecture
• • 3.1 (Key,Value) Vectors
  • 3.2 Range Push and Pull
  • 3.3 User-Defined Functions on the Server
  • 3.4 Asynchronous Tasks and Dependency
  • 3.5 Flexible Consistency
  • 3.6 User-defined Filters
  
  
• 4. Implementation
• • 4.1 Vector Clock
  • 4.2 Messages
  • 4.3 Consistent Hashing
  • 4.4 Replication and Consistency
  • 4.5 Server Management
  • 4.6 Worker Management
  
  
• 5 Evaluation
• • 5.1 Sparse Logistic Regression
  • 5.2 Latent Dirichlet Allocation
  • 5.3 Sketches
  
  
• 6 Summary and Discussion
• References
• 阅读总结

沐神的成名作谁能不爱&＃xff1f;这是沐神2014年发表在OSDI的文章&＃xff0c;一篇有关大规模分布式机器学习参数服务器的内容。大数据系统有很多&＃xff0c;比如通用领域的批处理系统MapReduce&＃xff0c;spark&＃xff0c;流处理系统storm&＃xff0c;spark Streaming&＃xff0c;当然也有特定领域的系统像图处理系统Giraph&＃xff0c;基于Spark的机器学习系统MLlib。本文的大数据系统是一个用于分布式机器学习问题的参数服务器框架&＃xff0c;开源后已经被亚马逊&＃xff0c;Facebook&＃xff0c;百度等多家顶级互联网公司应用。

本文提出了一个用于分布式机器学习问题的参数服务器框架。数据和任务都分布在工作节点上&＃xff0c;而服务器节点维护全局的共享参数&＃xff0c;表示为密集或稀疏的向量和矩阵。该框架管理节点之间的异步数据通信&＃xff0c;支持灵活的一致性模型&＃xff0c;具有弹性可扩展和持续容错特性。
实验部分为了证明框架的扩展性&＃xff0c;展示了PB级别的真实数据的实验结果&＃xff0c;其中包含数十亿示例和参数&＃xff0c;涉及从稀疏逻辑回归到潜在狄利克雷分配和分布式草图等问题。

分布式优化和推理正在成为解决大规模机器学习问题的先决条件&＃xff0c;现有的问题为&＃xff1a;

1. 规模&＃xff1a;数据增长&＃xff0c;模型复杂&＃xff0c;单一服务器难以解决&＃xff1b;
2. 算法&＃xff1a;高效的分布式算法不容易实现&＃xff1b;
3. 效率&＃xff1a;密集的计算量和数据通信需要复杂的系统设计。

训练数据的实际数量在1TB到1PB之间变化&＃xff0c;这允许人们设计




1



0


9




10^9


109到




1



0


12




10^12


1012参数规模的强大复杂的模型。这些模型通常由所有节点共享&＃xff0c;在执行计算时经常访问共享参数。共享带来三个挑战&＃xff1a;

1. 访问参数需要大量带宽&＃xff1b;
2. 许多机器学习算法是顺序进行的。当同步成本和机器延时较高会损害性能&＃xff1b;
3. 大规模条件下&＃xff0c;容错至关重要&＃xff0c;学习任务通常在云环境执行&＃xff0c;不同的机器可能会抢占作业。

上图是某数据中心作业情况&＃xff0c;其中任务失败是由于没有容错机制而导致被抢占或丢失机器。因此容错是工业界部署的必要条件&＃xff08;与研究不同&＃xff09;。

1.1 Contributions

本文是参数服务器的第三代开源实现&＃xff0c;着重于分布式推理的系统方面。它为开发人员提供了两个优势&＃xff1a;

• 通过分解出机器学习中常用的组件&＃xff0c;使特定应用程序代码简洁。
• 作为系统级优化的共享平台&＃xff0c;提供了一个健壮、通用和高性能表现的算法。

参数服务器提供了五个关键特性&＃xff1a;

1. 高效通信&＃xff1a; 异步通信不会阻塞计算&＃xff0c;针对机器学习任务进行优化&＃xff0c;减少网络流量和开销。
2. 灵活一致模型&＃xff1a; 宽松的一致性免去了同步成本和延迟影响。允许算法设计者权衡算法收敛速度和系统效率&＃xff0c;取决于数据、算法和硬件。
3. 弹性可扩展性&＃xff1a; 无需重启框架&＃xff0c;新节点可直接加入。
4. 容错性和耐久性&＃xff1a; 1s内从非灾难性机器学习故障中恢复并修复&＃xff0c;而不中断计算。向量时钟确保网络分区和故障前所定义好的行为不受影响。
5. 易用性&＃xff1a; 全局共享参数表示为向量和矩阵&＃xff0c;由于高性能多线程库处理线代数据类型&＃xff0c;有利于机器学习程序的开发。

本文所提出系统的新颖之处在于通过选择正确的系统技术&＃xff0c;将它们应用于机器学习算法并修改算法以使系统更加友好实现协同作用。特别地&＃xff0c;我们可以放松一些其他方面的硬件约束&＃xff0c;因为相关机器学习算法对扰动有很强的的容忍度。这样就得到了一个可以扩展到工业规模的通用ML系统。

在当时机器学习领域通用的系统如spark&＃xff0c;只能处理比较小规模的数据场景&＃xff0c;但是本文的参数服务器作为通用的分布式系统&＃xff0c;能够在工业界处理最大规模数据。

1.2 Engineering Challenges

在进行分布式数据分析时涉及读取和更新不同工作节点共享参数问题。参数服务器框架为工作节点之间的模型参数和统计信息之间的聚合同步提供了一种有效的机制。每个参数服务器仅维护一部分参数&＃xff0c;并且每个工作节点在运行时通常只需要这些参数的子集。在构建高性能参数服务器系统时出现了两个关键挑战&＃xff1a;

1. 通信&＃xff1a; 键值对存储参数的方式低效&＃xff0c;因为参数值可能很小&＃xff0c;并且将每个更新作为键值操作发送的开销很大。本文的解决方案从参数数据的表示形式&＃xff08;向量、矩阵、张量&＃xff09;入手&＃xff0c;每轮迭代更新通常是对象的一部分&＃xff0c;也就是说节点通常发送向量或矩阵的一部分&＃xff0c;这样参数服务器可以自动批处理更新&＃xff0c;并且高效实施一致性跟踪。
2. 容错&＃xff1a; 容错在大规模场景至关重要&＃xff0c;并且为了高效计算&＃xff0c;并不需要在一个节点上的长时间运行的计算。服务器之间参数的实时复制支持热故障转移。故障转移和自我修复分别将机器的移除或添加视为故障或修复&＃xff0c;从而支持动态扩展。

上图展示了在不同系统上执行最大监督和无监督学习实验的规模。很明显&＃xff0c;本文的系统能够在数量级更大的处理器上覆盖数量级更大的数据。

上表概述了几种机器学习系统的主要特性。本文的参数服务器在一致性上提供更多的灵活性&＃xff0c;并且是唯一提供持续容错机制的系统。原生的数据类型也对数据分析友好。

这里想谈谈上图的容错&＃xff0c;可以看到参数服务器是持续的容错&＃xff0c;而Graphlab等提供的是检查点等容错&＃xff0c;持续容错的优势是容错恢复快&＃xff0c;并且不像检查点那样&＃xff0c;要占用很多的空间存储检查点信息&＃xff0c;同时回退也会造成重复计算。

1.3 Related Work

亚马逊、百度、Facebook、谷歌、微软和雅虎已经实现了相关系统。第一代参数服务器缺乏灵活性并且性能不好&＃xff0c;它将高速缓存memcached键值分布式存储重新应用在同步机制。YahooLDA通过实现用户可定义的更新原语和更具原则性的负载分配算法实现专用服务器从而改进此设计。第二代参数服务器Distbelief是特定任务系统。Petuum迈出了通用平台的第一步。它使用有界延迟模型改进了YahooLDA&＃xff0c;同时对工作线程模型进一步限制。
将参数服务器和通用的机器学习分布式系统进行比较是有意义的。同步和迭代通信会随着节点的增多带来更多的挑战。基于Hadoop的Mahout和Spark的MLIib均采用迭代MapReduce框架。MLI的一个关键点在于迭代之间保持状态&＃xff0c;这是参数服务器的核心目标。
分布式GraphLab使用图形抽象来异步调度通信。它缺乏基于Map-reduce框架的弹性可扩展性&＃xff0c;依赖于粗粒度快照进行恢复&＃xff0c;这两者都阻碍了可扩展性。它对于某些算法的实用性受到缺乏作为有效的一流原语的全局变量同步的限制。本文的参数服务器的一个核心目标是获得GraphLab异步的优势&＃xff0c;同时不受框架限制。
Piccolo使用与参数服务器相关的策略来共享和聚集节点之间的状态。工作节点在本地预先聚集状态并将更新传输到保持聚合状态的服务器。它实现了本文系统很大一部分&＃xff0c;但是缺少专门的优化&＃xff1a;消息压缩&＃xff0c;复制和通过依赖图表示的变量一致性模型。

机器学习系统通常由三部分组成&＃xff1a;特征提取&＃xff0c;目标函数和学习。其中特征提取处理原始训练数据&＃xff0c;获得特征向量。

2.1 Goals

许多机器学习算法的目标可以通过“目标函数”来表达&＃xff0c;这个函数可以捕捉学习模型的属性。学习算法通常最小化目标函数来获得最终模型。通过多次迭代改进模型接近解决方案。当接近最优解或者模型收敛时停止迭代。此外&＃xff0c;训练数据可能非常大&＃xff0c;每个数据都可能表示为非常高维的特征向量。迭代处理如此大规模的数据需要巨大的计算和带宽资源&＃xff0c;并且&＃xff0c;每天可能会有更新数据添加到系统中&＃xff0c;这需要算法实时运行。如何高效执行是本文的主要关注点。下面介绍两种广泛使用的机器学习技术用来演示参数服务器的功效。

2.2 Risk Minimization

风险大体上是预测误差的一种度量&＃xff0c;是预测值与真实值之间的误差。训练由n个数据组成&＃xff0c;





x


i




x_i


xi​是第$i$个样本&＃xff0c;通常是长度为$d$的向量。每个训练样本





x


i




x_i


xi​与一个标签





y


i




y_i


yi​相关联。风险最小化可以学习一个预测未来示例$x$的标签的模型。
在任何学习算法中&＃xff0c;训练数据量与模型大小之间存在重要关系。一个更复杂的模型通常会提高准确性&＃xff0c;但是只能在一定程度上提高&＃xff0c;因为数据集数量不够的话会导致模型过拟合。另一方面&＃xff0c;一个太小的模型无法捕获对做出正确决策至关重要的数据的相关属性。
正则化风险最小化是寻找平衡模型复杂性和训练误差的一种方法。它通过最小化两个项的和来实现&＃xff1a;表示训练数据上的预测误差的损失$L(x,y,w)$和惩罚模型复杂性的正则化器$\Omega [w]$。一个好的模型是低错误和低复杂度的模型。所以努力最小化&＃xff1a;





F


(


w


)


&＃61;



∑



i


&＃61;


1



n



l


(



x


i



,



y


i



,


w


)


&＃43;


Ω


(


w


)



F(w)&＃61;\\sum^n_i&＃61;1l(x_i,y_i,w)&＃43;\\Omega(w)


F(w)&＃61;i&＃61;1∑n​l(xi​,yi​,w)&＃43;Ω(w)
在实验部分&＃xff0c;本文使用高性能分布式学习算法来评估参数服务器。为了简单起见&＃xff0c;这里先描述一个更简单的模型叫分布式次梯度下降。


如上图和算法1所示&＃xff0c;训练数据按块分发到所有节点上&＃xff0c;这些节点共同学习出参数向量$w$&＃xff0c;该算法迭代运行。在每次迭代中&＃xff0c;每个节点独立地使用自己的训练数据来确定应该对$w$进行哪些更新以接近最优值。由于每个节点的更新只反映它自己的训练数据&＃xff0c;所以系统需要一种机制来允许这些更新进行融合。它通过将这些更新表示为次梯度&＃xff08;参数向量$w$应移动方向&＃xff09;并在将所有次梯度应用于$w$之前聚合到一起。

算法1中开销最大的步骤是计算次梯度去更新$w$。这个任务被分配给所有的节点&＃xff0c;每个节点执行迭代任务。作为其中一部分&＃xff0c;节点计算





w


T




x



i


k





w^Tx_i_k


wTxik​​&＃xff0c;对于高维的$w$可能不可行。幸运的是&＃xff0c;当且仅当它的一些训练数据引用该条目时&＃xff0c;节点才需要知道$w$的坐标。例如在广告点击预测中&＃xff0c;如果只有极少数广告包含OSDI 2014短语&＃xff0c;那么大多数节点不会对$w$中的相应条目产生任何更新&＃xff0c;因此不需要此条目。尽管$w$的总大小可能超过单个机器的容量&＃xff0c;特定节点所需要的工作条目可以简单缓存在本地。上图显示&＃xff0c;对于100个节点&＃xff0c;每个节点只要需要总参数的7.8%&＃xff0c;当有10000个节点时&＃xff0c;降低到0.15%。

这里在看完沐哥的视频后&＃xff0c;才有了更深的理解&＃xff0c;为什么参数服务器需要多个服务器节点存储参数&＃xff0c;而工作节点只需要一个就行呢&＃xff1f;以及坐标是什么意思&＃xff1f;因为对于单个工作节点&＃xff0c;它只需要拿到一部分参数就可以在已有的数据集上进行训练了&＃xff0c;它所拥有的只是一部分数据&＃xff0c;只会更新一部分参数&＃xff0c;所以上面所描述的坐标&＃xff0c;就是指所需的那一部分参数在参数服务器中所在的位置。

2.3 Generative Models

无监督学习算法没有训练标签&＃xff0c;它的思想是试图捕获数据集的基础结构&＃xff0c;例如给定文档集合&＃xff0c;推测每个文档包含的主题。在推荐系统内容个性化等实际环境中&＃xff0c;这些问题的规模是巨大的&＃xff0c;这使得跨大型集群并行化算法变得至关重要。
由于上述问题的规模和数据量&＃xff0c;这些算法在引入第一代参数服务器才具有商业价值。主题模型的一个挑战在于参数描述当前估计文档应该是如何产生的必须要共享。一个热门的主题建模方法是潜在狄利克雷分布&＃xff08;LDA&＃xff09;。虽然统计模型是完全不同的&＃xff0c;但所得到的学习算法与算法1很相似。关键的区别在于更新步骤不是一个梯度计算&＃xff0c;而是模型对文档解释程度的估计。
计算需要访问每个文档的辅助元数据&＃xff0c;该元数据在每次访问文档时都会更新。由于文档的数量很大&＃xff0c;每当处理文档时&＃xff0c;通常都会从磁盘读取元数据并将其写回磁盘。辅助数据是分配给文档的主题集&＃xff0c;学习的参数$w$由单词出现的相对频率组成。
与监督学习一样&＃xff0c;每个节点只需要存储处理文档中出现的单词的参数&＃xff0c;因此可以处理比单个节点可处理的更大的模型。

参数服务器节点分组为一个服务器组和多个工作组&＃xff0c;如上图所示。
对于服务器组&＃xff1a;

1. 服务器组中的一个服务器节点维护全局共享参数的一个分区。
2. 服务器节点之间相互通信以复制或迁移参数以实现可靠性和可扩展性。
3. 服务器管理节点维护服务器数据一致性&＃xff0c;如节点的生命周期。

对于工作组&＃xff1a;

1. 每个工作组运行一个应用程序。
2. 节点通常在本地存储一部分训练数据用来计算局部统计数据如梯度。
3. 节点仅与服务器节点之间通信&＃xff0c;更新和共享参数。
4. 每个工作组都有一个调度程序节点&＃xff0c;分配任务并监控节点。

参数服务器支持独立的参数命令空间&＃xff0c;这允许工作组将其共享的参数集与其他组分离。当然不同工作组也可以共享命名空间&＃xff0c;可以用多个工作组并行处理深度学习应用。
参数服务器旨在简化分布式机器学习应用程序。

• 共享参数表示为(key, value)向量&＃xff0c;利于线性代数运算。
• 共享参数分布在一组服务器节点上。
• 任何节点都可以上传本地参数并从远程节点拉取参数。
• 默认情况下任务是工作节点执行&＃xff0c;也可以通过用户定义的函数分配给服务器节点。
• 任务是异步的并且并行运行。
• 参数服务器为算法设计者提供了灵活性&＃xff0c;可以通过任务依赖图和判断来选择一致性模型传输参数的子集。

3.1 (Key,Value) Vectors

节点之间共享的模型可以表示为一组键值对。例如在损失最小化问题中&＃xff0c;配对的是特征ID和权重&＃xff0c;在LDA中&＃xff0c;配对的是单词ID和主题ID以及计数。
本文的参数服务器通过识这些键值项的潜在含义改进了这种方法&＃xff1a;机器学习算法通常将这些模型视为线性代数对象&＃xff0c;比如在风险最小化中的参数$w$&＃xff0c;通过将这些对象视为稀疏线性代数对象&＃xff0c;参数服务器可以提供与键值对抽象的相同功能&＃xff0c;同时加入重要优化操作&＃xff0c;如向量加法、乘法&＃xff0c;计算2范数等其他精细操作。
为了支持这些优化&＃xff0c;假设key值是有序的。可以将参数视为键值对同时赋予它们向量和矩阵语义。有助于使用机器学习中的线性代数&＃xff0c;这减少了实现优化算法的编程工作量。此外&＃xff0c;这种接口设计利用CPU高效的多线程自调整线性代数库&＃xff08;BLAS、LAPACK等&＃xff09;实现高效的代码。

与一般的键值对不同&＃xff0c;这里的key是int64或int128&＃xff0c;value是一串浮点数&＃xff0c;可以理解成向量&＃xff0c;可以用一些数值运算库直接处理。

3.2 Range Push and Pull

节点之间采用push和pull传输数据。算法1中每个节点将其整个局部梯度推送到服务器中&＃xff0c;然后将更新的权重拉取回来。算法3中更高级的算法采用相同的模式&＃xff0c;只是每次通信一定范围的keys。
参数服务器通过支持基于范围的推和拉来优化这些更新&＃xff0c;以方便程序员&＃xff0c;同时提高计算和网络带宽效率。如果$\mathcal{R}$是一个key范围&＃xff0c;$w.push(\mathcal{R},\mathrm{dest})$表示从$\mathcal{R}$范围内key表示的所有$w$的现有条目发送给目标&＃xff0c;目标可以是特定节点&＃xff0c;也可以是服务器组等节点组。$w.pull(\mathcal{R},\mathrm{dest})$执行相反的操作。
这个接口可以扩展通信任何共享相同key的本地数据结构。比如在推送本地梯度可以用$w.push(\mathcal{R},\mathrm{g},\mathrm{dest})$来减少内存同时享受其他的优化。

3.3 User-Defined Functions on the Server

服务器节点可以执行用户自定义函数&＃xff0c;这是因为服务器节点有共享参数更完整和更新的信息。算法1中&＃xff0c;服务器节点评估次正则项$$\Omega$$的次梯度以便更新$$w$$。在5.3的草图中&＃xff0c;几乎所有的操作都发生在服务器端。

3.4 Asynchronous Tasks and Dependency

• 任务由远程程序调用&＃xff1a;可以是节点向服务器发送的push、pull操作&＃xff0c;也可以是调度程序发送给任何节点的用户定义函数。
• 任务是异步执行的&＃xff1a;调度者可以在发出任务后进行进一步的计算。
• 任务完成&＃xff1a;调度者收到被调度者的回复才标记为完成。
• 依赖关系&＃xff1a;上图描述了任务之间依赖关系&＃xff0c;任务10和11是相互独立的&＃xff0c;但是任务12取决于11。也就是说&＃xff0c;为了最佳性能任务并行执行&＃xff0c;但是任务之间的依赖关系可以在任务之间放置。

3.5 Flexible Consistency

独立任务通过并行使用 CPU、磁盘和网络带宽来提高系统效率。但是&＃xff0c;这可能会导致节点之间的数据不一致。比如上图迭代11用的是旧的迭代10&＃xff0c;会获得与迭代10中相同的梯度。这种不一致会降低算法1的迭代速度。不过一些算法对这种不一致不太敏感。比如在算法3中&＃xff0c;每次只更新$$w$$的一部分&＃xff0c;这样只会导致一部分不一致。
系统效率和算法收敛速度之间的权衡通常取决于多种因素&＃xff0c;包括&＃xff1a;算法对数据一致性的敏感度、训练数据特征相关性以及硬件组件容量差异。
参数服务器为算法设计者提供了定义一致性模型的灵活性。这里展示了三种根据任务依赖性实现的不同模型。有向无环图如下所示&＃xff1a;

1. 顺序模型&＃xff1a; 所有任务都是逐个执行&＃xff0c;产生的效果和单线程相同。
2. 最终模型&＃xff1a; 所有任务独立进行&＃xff0c;适合算法对延迟具有鲁棒性。
3. 有界延迟模型&＃xff1a; 设置最大延迟时间T&＃xff0c;一个任务被阻塞&＃xff0c;直到T时间前的任务完成。延迟大&＃xff0c;性能好&＃xff0c;收敛慢&＃xff0c;延迟小&＃xff0c;性能差&＃xff0c;收敛快。

依赖关系图可以是动态的&＃xff0c;调度器可以根据运行进度调整延迟&＃xff0c;以平衡系统效率和底层优化算法的收敛。

3.6 User-defined Filters

参数服务器支持用户自定义过滤器选择同步单个键值对&＃xff0c;从而对任务中数据的一致性进行细粒度控制。优化算法本身需要分析出哪些参数对同步信息最有用。在5.1节会详细讨论KKT过滤器。

服务器采用一致性哈希存储键值对参数。为了容错&＃xff0c;条目采用链复制进行复制&＃xff0c;与之前的键值对系统不同&＃xff0c;参数服务器针对基于范围的通信和基于范围的向量时钟进行了压缩优化。

4.1 Vector Clock

考虑到潜在复杂的任务依赖关系图和快速恢复的需要&＃xff0c;每个键值对都与一个向量时钟关联&＃xff0c;该向量时钟记录每个单独节点在该键值对上的时间。虽然向量时钟很便捷&＃xff0c;但是其简单实现需要$O(nm)$空间去处理$n$个节点和$m$个参数。这在内存和带宽上是不可行的。
由于参数服务器基于范围的通信模式&＃xff0c;许多参数具有相同的时间戳。如果一个节点在一个范围内推送参数&＃xff0c;那么与节点相关联的时间戳很可能相同。这些时间戳可以被压缩为一个单一范围的向量时钟。
初始状态对于每个节点$i$只有一个范围的向量时钟&＃xff0c;覆盖整个参数key空间。每个范围集可以拆分出最多3个新的向量时钟。设$k$是算法传递唯一范围的总数&＃xff0c;那么最多有$O(mk)$个向量时钟&＃xff0c;$m$是节点的个数。这显著减少了范围向量时钟所需的空间。

比如在语言模型中&＃xff0c;模型有几十或者几百层&＃xff0c;在做vector clock计时&＃xff0c;只需要计算每个节点在每一层用的是哪个时间的值&＃xff0c;这样存储量就大大减少。

4.2 Messages

节点可以将消息发送给单个节点或者节点组。消息格式如下&＃xff1a;





[



v


c




(


R


)



,


(



k


1



,



v


1



)


,


.


.


.


,


(



k


p



,



v


p



)


]



k


j



∈


R



a


n


d



j


∈





1


,


.


.


.


,


p






[\\rm vc\\mathcal(R),(k_1,v_1),...,(k_p,v_p)] k_j \\in \\mathcalR \\rm and j \\in \\ 1,...,p\\


[vc(R),(k1​,v1​),...,(kp​,vp​)]kj​∈Randj∈1,...,p
这是参数服务器基本的通信格式&＃xff0c;同时适用于共享参数和任务。
消息可以携带范围$\mathcal{R}$内所有可用key的子集&＃xff0c;缺失的key被分配相同的时间戳而不改变它们的值。

• 值缓存&＃xff1a;由于机器学习通常需要高带宽&＃xff0c;信息压缩是必不可少的。训练数据在迭代之间通常保持不变&＃xff0c;因此服务器节点需要缓存key列表&＃xff0c;这样发送方只需要发送列表的哈希值而不是列表本身。
• 压缩零&＃xff1a;值通常包含很多零条目&＃xff0c;这有用户定义的过滤器清零也有稀疏向量中的零。因此通常只需要发送非零键值对&＃xff0c;可以用快速Snappy压缩库来压缩消息&＃xff0c;有效清除零。

4.3 Consistent Hashing

keys和服务器节点ID都被嵌入到哈希环中&＃xff0c;每个服务器节点管理从其插入点开始到逆时针方向下一个节点的插入点的key范围&＃xff0c;称为主节点。物理服务器通常通过多个虚拟服务器在环中表示&＃xff0c;以改善负载平衡和恢复。

4.4 Replication and Consistency

每个服务器节点存储着相对于自己拥有的k个逆时针方向的邻居keys范围的副本。我们把保存副本的节点称为对应键范围的从节点。上图左边展示了一个k&＃61;2的例子&＃xff0c;服务器1复制了服务器2和服务器3拥有的键范围。
工作节点与主节点通信&＃xff0c;主节点上任何修改都会同步复制到从节点上。上图显示了工作节点1将x推送到服务器1的情况&＃xff0c;只有确认数据修改复制到从节点上才完成推送任务。
原始的复制会让网络带宽增加k倍。参数服务器允许聚合后复制。如上图右边所示。虽然聚合增加了任务回复的延迟&＃xff0c;但是可以通过宽松的一致性条件来避免。

4.5 Server Management

为了实现容错和动态扩展&＃xff0c;必须支持节点的添加和删除。当加入一个服务器时&＃xff0c;步骤如下&＃xff1a;

1. 服务器管理器为新节点分配一个键范围以充当主节点。这可能会导致另一个键范围分裂或从终止的节点中删除。
2. 该节点获取数据范围并作为主节点进行维护&＃xff0c;同时维护k个从节点。
3. 服务器管理器广播节点的更改。消息得接受者根据key范围收缩他们自己的数据&＃xff0c;并将未完成的任务交给新的节点。
   从某个节点S获取范围$\mathcal{R}$中的数据分为两个阶段进行。

• 第一阶段&＃xff1a;S预复制范围内的键值对和对应的向量时钟&＃xff0c;这可能会导致算法2中的时钟分裂。
• 第二阶段&＃xff1a;S不再接收影响key范围的$\mathcal{R}$消息&＃xff0c;同时S向新节点发送在预复制阶段$\mathcal{R}$中发生的所有更改。

在收到节点更改消息时&＃xff0c;节点N首先检查是否也维护key范围$\mathcal{R}$&＃xff08;现在归新节点维护&＃xff09;。如果不再维护就把相关联的所有键值对和向量时钟删除。接下来对于尚未收到回复的消息&＃xff0c;如果键值范围与




R